﻿


namespace Common.Algorithm.Core;

/// <summary>
/// 退火算法
/// </summary>
public class AnnealService
{
    double temperature = 10E6;
    double decay = 0.0001;

    public int[] path { get; set; }

    public List<int> bestPath = new List<int>();

    public static Random randomBuilder = new Random();
    public static MatrixBuilder<double> matBuilder { get; set; } = Matrix<double>.Build;

    static Matrix<double> matrixDistance;

    public AnnealService(IEnumerable<GraphEdge> edges)
    {
        var groups = edges.GroupBy(e => e.stVertexId);
        var cityNum = groups.Count();
        matrixDistance = matBuilder.Dense(cityNum, cityNum);

        for (int i = 0; i < cityNum; i++)
        {
            for (int j = 0; j < cityNum; j++)
            {
                matrixDistance[i, j] = i == j ? 0 : edges.At(i, j).weight;
            }
        }

        path = new int[cityNum];
        for (int i = 0; i < cityNum; i++)
        {
            path[i] = i;
        }
        bestPath = path.ToList();
    }
    public AnnealService(Matrix<double> _matrixDistance)
    {
        matrixDistance = _matrixDistance;
        int cityNum = _matrixDistance.RowCount;
          
        path = new int[cityNum];
        for (int i = 0; i < cityNum; i++)
        {
            path[i] = i;
        }
        bestPath = path.ToList();
    }


    public void RunAlgm(int numberOfGeneration)
    {
        var curPath = path;

        while (numberOfGeneration > 0 || temperature > 1)
        {
            numberOfGeneration--;
            temperature = temperature * (1 - decay);


            var curDist = PathLength(curPath);
            var newPath = SwitchRandom(curPath);
            var newDist = PathLength(newPath);

            var judge = JudgeFunc(curDist, newDist);

            var threshold = randomBuilder.Next(100) * 0.01;
            if (judge > threshold)
            {
                curPath = newPath;
            }
        }

        bestPath = curPath.ToList();
    }

    /// <summary>
    /// 评价函数
    /// </summary>
    /// <param name="curDist"></param>
    /// <param name="newDist"></param>
    /// <returns></returns>
    public double JudgeFunc(double curDist, double newDist)
    {
        var deltaDist = newDist - curDist;

        if (deltaDist < 0)
        {
            return 1;
        }
        else
        {
            var tmpp = 1 / Math.Exp(deltaDist / temperature);
            return tmpp;
        }
    }


    /// <summary>
    /// 计算当前路径的总路程
    /// </summary>
    /// <param name="_paths"></param>
    /// <returns></returns>
    public static double PathLength(int[] _paths)
    {
        double pathSum = 0;
        for (int i = 0; i < _paths.Length - 1; i++)
        {
            pathSum += matrixDistance[_paths[i], _paths[i + 1]];
        }
        return pathSum;
    }


    /// <summary>
    /// 随机互换
    /// </summary>
    /// <param name="_paths"></param>
    /// <returns></returns>
    public int[] SwitchRandom(int[] _paths)
    {
        var index1 = randomBuilder.Next(0, _paths.Count());
        var index2 = randomBuilder.Next(0, _paths.Count());
        while (index1 == index2)
        {
            index2 = randomBuilder.Next(0, _paths.Count());
        }

        int tmp1 = _paths[index1];
        int tmp2 = _paths[index2];

        _paths[index1] = tmp2;
        _paths[index2] = tmp1;

        return _paths;
    }

}
